iT邦幫忙

2021 iThome 鐵人賽

DAY 26
0
自我挑戰組

Leetcode刷題筆記系列 第 26

[Day 26] Leetcode 283. Move Zeroes (C++)

  • 分享至 

  • xImage
  •  

前言

TGIF!今天來個簡單題休息一下~283. Move Zeroes。這題是要用inplace的方式來把0移到數列的後面。

想法

如果不管不要make a copy,簡單的方式就是建立一個vector,遍歷一遍原本的array,看到不是0的就把它push back到vector裡,後面都補0就好了~
不過看到inplace不要make copy,第一個就想到swap的方式,想到的方法是遍歷的時候看到是0的話就跟它後面第一個不是0的數做交換,所以一開始寫了一個沒有優化的版本,慢到看不到別的解法的車尾燈~

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // if 0, search for the next >0 integer
        for(int i=0;i<nums.size();++i){
            if(nums[i]==0){
                // search for the next elements not equal 0
                int j=i;
                while(nums[j]==0 & j<nums.size()-1){
                    ++j;
                }
                swap(nums[i],nums[j]);
            }
        }
    }
};

裡面有些浪費時間的地方,例如說我每次都重新從i的地方開始找下個非0的數,但如果我前一次找到發現上一個非0已經遠遠在i的後面,就不用再從i開始找了,從上一個地方開始找就好,優化如下:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j=0;
        for(int i=0;i<nums.size();++i){
            if(nums[i]==0){
                // search for the next elements not equal 0
                j=max(j,i);
                while(nums[j]==0 & j<nums.size()-1){
                    ++j;
                }
                swap(nums[i],nums[j]);
            }
        }
    }
};

速度快了30倍左右。
附上另外一種解如下

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
       int j = 0;
       for(int i = 0; i < nums.size(); i++){
          if(nums[i] != 0)
          {
              swap(nums[i], nums[j++]);
          }
      }
  }
};

這個解法反過來是!=0的時候進行swap,為什麼可以這樣做?其實它的j就是紀錄目前非0個數(!=0就j++),因此目前掃到的nums[i]就依序換到第j個非0個數的位置。

結語

明天再回歸sum系列吧~


上一篇
[Day 25] Leetcode 287. Find the Duplicate Number (C++)
下一篇
[Day 27] Leetcode 207. Course Schedule (C++)
系列文
Leetcode刷題筆記30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言